import functools

# 记忆化搜索
class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        M = len(dungeon)
        N = len(dungeon[0])
        @functools.cache
        def search(i, j):
            if i == M - 1:
                if j == N - 1:
                    if dungeon[i][j] < 0:
                        return -dungeon[i][j] + 1
                    else:
                        return 1
                else:
                    if dungeon[i][j] >= search(i, j + 1) - 1:
                        return 1
                    else:
                        return search(i, j + 1) - dungeon[i][j]
            else:
                if j == N - 1:
                    if dungeon[i][j] >= search(i + 1, j) - 1:
                        return 1
                    else:
                        return search(i + 1, j) - dungeon[i][j]
                else:
                    need = min(search(i + 1, j), search(i, j + 1))
                    if dungeon[i][j] >= need - 1:
                        return 1
                    else:
                        return need - dungeon[i][j]
        return search(0, 0)

# 遍历法
# class Solution(object):
#     def calculateMinimumHP(self, dungeon):
#         """
#         :type dungeon: List[List[int]]
#         :rtype: int
#         """
#
#         @functools.cache
#         def search(i, j):
#             now_health = []
#             now_init_health = []
#             health = []
#             init_health = []
#             if i == 0 and j == 0:
#                 if dungeon[i][j] <= 0:
#                     health = [1]
#                     init_health = [- dungeon[i][j] + 1]
#                 else:
#                     health = [dungeon[i][j] + 1]
#                     init_health = [1]
#             else:
#                 if i != 0:
#                     last_health, last_init_health = search(i - 1, j)
#                     now_health += last_health
#                     now_init_health += last_init_health
#                 if j != 0:
#                     last_health, last_init_health = search(i, j - 1)
#                     now_health += last_health
#                     now_init_health += last_init_health
#                 for k in range(len(now_health)):
#                     if now_health[k] + dungeon[i][j] <= 0:
#                         health.append(1)
#                         init_health.append(now_init_health[k] - now_health[k] - dungeon[i][j] + 1)
#                     else:
#                         health.append(now_health[k] + dungeon[i][j])
#                         init_health.append(now_init_health[k])
#             return health, init_health
#
#         return min(search(len(dungeon) - 1, len(dungeon[0]) - 1)[1])

data = Solution()
dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
print(data.calculateMinimumHP(dungeon))
dungeon = [[-6, -10], [1, 4]]
print(data.calculateMinimumHP(dungeon))
dungeon = [[100]]
print(data.calculateMinimumHP(dungeon))
dungeon = [[3,-20,30],[-3,4,0]]
print(data.calculateMinimumHP(dungeon))
